﻿/************************************************************
*
* 命名空间：Deep.Algorithm.Sorting
* 文件名称：ShellSort.cs
* 创建者：王嘉庆
* 创建日期：2021-05-28 07:14:40
* 邮箱：1101202419@qq.com
* 博客：https://blog.csdn.net/wuxinwudai
* 功能描述：
* 使用说明：
* 最后更新日期：
*************************************************************/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Deep.Algorithm.Sorting
{
    /// <summary>
    /// 希尔排序，由插入排序改良，插入排序移动间隔为1，希尔排序通过减少交换次数提高性能（直接交换了i与i+gap 的元素，中间的元素被跨过）
    /// 最坏时间复杂度为O(n3/2)，不是稳定算法
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class ShellSort : SortAlgorithm
    {
        public override T[] Sort<T>(T[] arr)
        {
            // gap 为增量
            for (int gap = arr.Length/2 - 1; gap > 0; gap/=2)
            {
                // 从第 gap 个元素逐个多其所在组进行插入排序
                for (int i = gap; i < arr.Length; i++)
                {
                    int j = i;
                    T tmp = arr[j];
                    if (arr[j-gap].CompareTo(arr[j])> 0)
                    {
                        while (j-gap > 0 && tmp.CompareTo(arr[j-gap])< 0)
                        {
                            arr[j] = arr[j - gap];
                            j -= gap;
                        }

                        arr[j] = tmp;
                    }
                }
            }
            return arr;
        }
    }
}
